package utils;


/**
 * Description：数组的最长公共子序列
 * Author: zhangc
 * Date：2017/9/19 22:30
 */
public class LargestAddSeq {

    public static void main(String[] args) {
        int[] arr = {1, 4, 3, 4, 8, 6, 9};
        System.out.println(getMaxLength(arr));
    }


    //获取连续递增子序列的最大长度
    public static int getMaxLength(int[] array) {
        int max = 0;
        array = getDP(array);
        for (int k = 0; k < array.length; k++) {
            if (array[ k ] > max)
                max = array[ k ];
        }
        return max;
    }


    //求 连续递增子序列状态[1,2,3,3,4,4,5,4]
    //数组中最大的值即为 最长串的长度
    public static int[] getDP(int[] array) {
        int[] dp = new int[ array.length ];
        for (int i = 0; i < array.length; i++) {
            dp[ i ] = 1;
            for (int j = 0; j < i; j++) {
                if (array[ j ] < array[ i ] && (dp[ j ] + 1 > dp[ i ]))
                    dp[ i ] = dp[ j ] + 1;
            }
        }
        return dp;
    }

}
